import { Compare, defaultCompare, swap } from '../../util';

/**
 * 冒泡排序(bubble-sort)：每轮都比较数组里相邻两项，如果左项大于右项就交换彼此，目的是
 * 每轮都让最大的移到数组末尾，所有轮结束后数组就是升序排序的了（降序是将最小移到末尾）。
 * @param array 原数组
 * @param compareFn 比较函数，默认升序
 * 值得注意的是，在每轮都将最大的冒泡到末尾后，在下一轮时是无需再处理末尾项了，所以在内部
 * 循环时要记得减去 i 。还有就是如果某轮里，没有交换过左右项，那么可以提前退出算法，
 * 因为上一轮排完凑巧就排完了。平均、最差场景的时间复杂度是O(n^2)，最好情况是O(n)；
 * 空间复杂度是O(1)，相邻项交换是常量级的临时空间。
 */
export function bubbleSort<T>(array: T[], compareFn = defaultCompare) {
    // 数组长度
    const length = array.length;
    // 长度不足2无需排序
    if (length < 2) {
        return array;
    }
    // 对数组的进行length次处理（其实length-1次就够了，因为是比较j和j+1这两项）
    for (let i = 0; i < length; i ++) {
        // 交换状态
        let hasSwap: boolean = false;
        // 减i是因为每轮都把最大的冒泡到末尾了，下一轮无需再处理它了；减1是保证合法取到“j + 1”项
        for (let j = 0; j < length - i - 1; j ++) {
            // compareFn默认是升序，使用Compare.BIGGER_THAN意思是，预期array[j]会更大
            if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
                swap(array, j, j + 1);
                hasSwap = true;
            }
        }
        /*
            如果某一轮里没有冒泡交换过，代表已经提前排好顺序了。
            这是冒泡排序最佳时间复杂度为O(N)的原因，其他情况都是O(N^2)
        */
        if (!hasSwap) {
            break;
        }
    }
    return array;
}
